\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url}
\usepackage{fullpage}


% Old Stuff
%%\oddsidemargin=0.15in
%%\evensidemargin=0.15in
%%\topmargin=-.5in
%%\textheight=9in
%%\textwidth=6.25in

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Instructor:
Jing Chen}{Teaching Assistant: Tao Xiao}{Handout #1: #3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}
\handout{2}{July 1, 2013}{Problem Set 1}

%This course is an undergraduate introduction to computational game theory, with emphasis on mechanism design.

\textbf{Due by Monday, July 8, 8am.}

\paragraph{Problem 1 (10pt).} 
\begin{itemize}
\item[(a)] How many (mixed) Nash equilibria does the Rock-Paper-Scissors game have? Prove your answer.

\item[(b)] Find a (mixed) Nash equilibrium of the BoS game other than the pure ones shown in class, and prove that it is an equilibrium. 

\item[(c)] How many equilibria does the BoS game have? Prove your answer.

\item[(d)] Construct an infinite normal-form game (that is, the players have infinitely many strategies) that does not have any (pure or mixed) equilibrium, and prove the correctness of your construction.
\end{itemize}

\paragraph{Problem 2 (10pt).} (OR94, Exercises 18.2 and 18.3.) An object is to be assigned to a player in the set $\{1,\dots,n\}$ in exchange for a payment. Player $i$'s valuation of the object is a positive integer $v_i$, and $v_1>v_2>\cdots > v_n$. The rule to assign the object is a (sealed-bid) auction: the players simultaneously submit bids (non-negative integers), and the object is given to the player with the lowest index among those who submit the highest bid, in exchange for a payment. A player who does not win does not pay.

\begin{itemize}
\item[(a)] In a {\em first price} auction the payment that the winner makes is his own bid. A player's utility is his valuation minus his payment if he gets the object, and is 0 otherwise.

Formulate a first price auction as a normal-form game and analyze all of its pure Nash equilibria. In particular, show that in all equilibria player 1 obtains the object.

\item[(b)] In a {\em second price} auction the payment that the winner makes is the highest bid among those bids of the players who do not win (so that if only one player submits the hghest bid then the price paid is the {\em second} highest bid).

Show that in a second price auction the bid $v_i$ of any player $i$ is a {\em weakly dominant} strategy: player $i$'s utility when he bids $v_i$ is {\em at least as high as} his utility when he bids any other number, regardless of the strategies of the other players. You should first formalize weak dominance following our definition of strict dominance.

Show that nevertheless there are (``inefficient") equilibria in which the winner is not player 1.
\end{itemize}

\paragraph{Problem 3 (10pt).} Consider the following game. Each of 15 students simultaneously announces a number in the set $\{1, 2, \dots, 100\}$. A prize of \$1 is split equally between all students whose number is closest to 1/3 of the class average.
%\begin{itemize}
%\item[(a)] 
Provide a sequence $(S^0, S^1, \dots, S^K)$ of iterated elimination of strictly dominated strategies.

%\item[(b)] Show that the game has a unique Nash equilibrium (in pure or mixed strategies).
%\end{itemize}
%
%\paragraph{Problem 3.} In the normal-form game below player 1 chooses rows, player 2 chooses columns, and player 3 chooses matrices. We only indicate player 3's utility. Show that action $D$ is not a best response for player 3 to any independent belief about his opponents' plays (i.e., mixed strategies for players 1 and 2), but that $D$ is not strictly dominated. Comment.
%\begin{center}
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & 9                     & 0                      \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & 0                     & 0                      \\ [1ex] \cline{2-3}
%\multicolumn{3}{c}{}                                                  \\ [-2ex]
%\multicolumn{1}{c}{} & \multicolumn{2}{c}{$A$} \\
%\end{tabular}
%$\quad\quad$
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & 0                     & 9                      \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & 9                     & 0                      \\ [1ex] \cline{2-3}
%\multicolumn{3}{c}{}                                                  \\ [-2ex]
%\multicolumn{1}{c}{} & \multicolumn{2}{c}{$B$} \\
%\end{tabular}
%$\quad\quad$
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & 0                     & 0                      \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & 0                     & 9                      \\ [1ex] \cline{2-3}
%\multicolumn{3}{c}{}                                                  \\ [-2ex]
%\multicolumn{1}{c}{} & \multicolumn{2}{c}{$C$} \\
%\end{tabular}
%$\quad\quad$
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & 6                     & 0                      \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & 0                     & 6                      \\ [1ex] \cline{2-3}
%\multicolumn{3}{c}{}                                                  \\ [-2ex]
%\multicolumn{1}{c}{} & \multicolumn{2}{c}{$D$} \\
%\end{tabular}
%\end{center}
%%M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.
%
%N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds). {\em Algorithmic game theory.} Cambridge University Press, 2007. (Available at \url{http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf}.)

\end{document}








